package leetcode.tree;

import leetcode.common.entitys.TreeNode;
import leetcode.common.utils.BtreeUtils;

import java.util.*;

/*
144. 二叉树的前序遍历

给定一个二叉树，返回它的 前序 遍历。

 示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
*/

public class PreorderTraversal144 {

    public static void main(String[] args) {
        Integer[] s = new Integer[]{1,null,2,3};
//        Integer[] s = new Integer[]{1,4,3,2};

        TreeNode root = BtreeUtils.buildBinaryTreeByArray(s, 0);;

        System.out.println(Arrays.toString(s));
        System.out.println(test(root).toString());
    }

    public static List<Integer> test(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        // 递归版本
        //preorderTraversalRecursive(root, list);

        // 非递归版本
        preorderTraversalNonRecursive(root, list);

        return list;
    }

    private static void preorderTraversalRecursive(TreeNode node, List<Integer> list) {
        if(null == node)
            return;

        list.add(node.val);
        preorderTraversalRecursive(node.left, list);
        preorderTraversalRecursive(node.right, list);
    }

    private static void preorderTraversalNonRecursive(TreeNode root, List<Integer> list) {
        LinkedList q = new LinkedList();
        q.push(root);
        while(null != root && 0 < q.size()) {
            root = (TreeNode) q.pop();
            list.add(root.val);
            if(null != root.right)
                q.push(root.right);
            if(null != root.left)
                q.push(root.left);
        }
    }
}
